﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/sort-an-array/
/*
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。

 

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
 

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
*/

// 开始解题：
// 方法1——快速排序三路划分版
// 交换
void Swap(int* a, int* b) {
	assert(a && b);
	int temp = *a;
	*a = *b;
	*b = temp;
}

// 三数取中
int GetMid(int* array, int left, int right) {
	assert(array);
	int mid = left + (right - left) / 2;
	if (array[mid] <= array[left] && array[left] <= array[right]) {
		return left;
	}
	if (array[right] <= array[left] && array[left] <= array[mid]) {
		return left;
	}

	if (array[left] <= array[mid] && array[mid] <= array[right]) {
		return mid;
	}
	if (array[right] <= array[mid] && array[mid] <= array[left]) {
		return mid;
	}
	return right;
}

// 快速排序三路划分版本
void Qsort(int* array, int left, int right) {
	assert(array);
	if (left >= right) {
		return;
	}
	int mid = GetMid(array, left, right);
	Swap(&array[left], &array[right]);
	int key = array[left];
	int Left = left;
	int cur = left + 1;
	int Right = right;
	while (cur <= Right) {
		if (array[cur] < key) {
			Swap(&array[Left], &array[cur]);
			cur++;
			Left++;
		}
		else if (array[cur] > key) {
			Swap(&array[cur], &array[Right]);
			Right--;
		}
		else {
			cur++;
		}
	}
	Qsort(array, left, Left - 1);
	Qsort(array, Right + 1, right);
}


int* sortArray(int* nums, int numsSize, int* returnSize) {
	*returnSize = numsSize;
	Qsort(nums, 0, numsSize - 1);
	return nums;
}